归并排序

归并排序的基本思想也是分治法。与快速排序不一样的是，归并排序是先分后治，而快排是先治后分

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现。

分

在分的阶段可以采用递归方法实现:

void mergeSort(int *arr,int start,int end){
    if(start>=end)return;//递归结束条件
    //分
    int mid=start+(end-start)/2;//将数组从中间分开
    mergeSort(arr,start,mid);
    mergeSort(arr,mid+1,end);
    //治
    merge(arr,start,mid,end,temp);//合并两个有序数组arr[start,mid]和arr[mid+1,end]到数组temp
}

治

在治的阶段将问题转化为了合并相邻有序子序列：

例如，｛８｝和｛４｝｛４，８｝和｛５，７｝｛４，５，７，８｝和｛１，２，３，６｝

void merge(int *arr,int start,int mid,int end,int *temp){
    int i=start;　//左序列指针
    int j=mid+1; //右序列指针
    int k=0; //临时数组指针
    while(i<=mid && j<=end){
        temp[k++]=((arr[i]<arr[j])?arr[i++]:arr[j++]);
    }
    while(i<=mid){
        temp[k++]=arr[i++];
    }
    while(j<=end){
        temp[k++]=arr[j++];
    }
    k=0;
    while(start<=end){　//小于等于
        arr[start++]=arr[k++];
    }
}

时间复杂度：

合并操作merge()的平均复杂度是$O(N)$

拆分操作是完全二叉树的深度，时间复杂度是$O(NlogN)$

所以，最坏、最好和平均时间复杂度都是$O(NlogN)$。

稳定排序

优缺点

缺点：需要额外的空间。开辟与arr数组一样大小的空间来存储排好的序列。

参考